专题·扩展欧几里得定理【including 求解二元一次方程,线性同余方程 | 您所在的位置:网站首页 › 辗转取余法 百科 › 专题·扩展欧几里得定理【including 求解二元一次方程,线性同余方程 |
初见安~这里是基础数论专题(3)~【详见数论专栏】 p.s:本文章假设你已经掌握了欧几里得算法——辗转相除法求最大公约数(gcd) 一、二元一次方程形如 很显然,一般的二元一次方程的解都是有很多组的,并没有唯一解。 我们先不讨论其他的,尝试一下解方程的整数解:) 我们知道,在辗转相除法中,gcd(a,b)=gcd(b,a % b)。而取余的操作又可以写成:a - a / b * b(这里是整除),所以带入原式子可以得到: 再由此可得: 而x‘ 和y'在辗转相除法中都可以逆推回来,也就是说可以得到这么一个表格: 以99x + 78y = 6为例 aba/bxy99781-2228782136-2221151-4615622-46320230NA20左边两列由上往下通过辗转相除法推出,靠右两列从下往上通过刚才得出的公式推出,得到一组特解:x = -22, y = 28。
那么如何表示出所有的解呢? 很明显的,在特解(x0, y0)的基础上,其余均有(x0 + d1 * k, y0 + d2 * k)(k为整数)作为解成立。即
所以可以表示得到: 所以方程的解就可以表示为: 如上述例子中,x0 = -22,y0 = 28,则通解为:(-22 + 26k, 28 - 33k)(k为整数)。 如此解法,就是扩展欧几里得定理。 代码实现的话直接套用我们表格旁的公式,递归gcd后回溯时计算即可。【记得保存x'】 二、线性同余方程形如 x为同余方程a关于b模n的解。也就是说ax和b同余。x一定为整数。 那么线性同余方程如何求解呢?首先我们观察—— 但是这里有一个问题——同余和二元一次方程还是有区别的,同余的话不一定有解。在欧几里得定理的基础上,我们可以求得 那么如果有解呢——因为同余方程有个取余的操作,也就是说x % d = x,(x + d)%d=x。所以如果有解,则恰好有gcd(a,n)个解。 求解同余方程的时候一定要注意一个问题——你求的ax + ny到底是b还是gcd(a, n),因为这涉及到一个到底是处理结果x还是处理a、n的问题,一定要小心。 代码的话就在扩欧的最后特判是否有解即可,具体操作具体到题目上。 关于求同余方程最小正整数解的问题,在逆元(传送门建设中)讲解后补充上~ 迎评:) ——End—— |
CopyRight 2018-2019 实验室设备网 版权所有 |